#include "TreeNode.h"
#include <queue>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
string serialize(TreeNode* root) {
    if (root == nullptr) {
        return "";
    }
    queue<TreeNode*> q;
    string ret;
    while (!q.empty()) {
        int level_size = q.size();
        for (int i = 0; i < level_size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            if (node == nullptr) {
                ret + "null,";
            } else {
                ret += std::to_string(node->val) + ",";
                q.push(node->left);
                q.push(node->right);
            }
        }
    }
    ret.pop_back();
    return ret;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if (data.empty()) {
        return nullptr;
    }
    vector<string> nodes = split(data, ',');
    TreeNode* root = new TreeNode(std::stoi(nodes[0]));
    queue<TreeNode*> q;
    q.push(root);
    for (int i = 1; i < nodes.size()-1; ++i) {
        TreeNode* node = q.front();
        q.pop();
        if (nodes[i] == "null") {
            node->left = nullptr;
        } else {
            node->left = new TreeNode(std::stoi(nodes[i]));
            q.push(node->left);
        }
        i++;
        if (nodes[i] == "null") {
            node->right = nullptr;
        } else {
            node->right = new TreeNode(std::stoi(nodes[i]));
            q.push(node->right);
        }
    }
    return root;
}

    vector<string> split(const string& s, char delimit) {
        stringstream ss(s);
        string token;
        vector<string> tokens;
        while (std::getline(ss, token, delimit)) {
            tokens.emplace_back(token);
        }
        return tokens;
    }

